package com.leetcode.tree.bst;

import com.leetcode.basic.TreeNode;

/**
 * @author Dennis Li
 * @date 2020/9/14 21:02
 */
public class ValidBST_98 {

    Integer pre;

    boolean result;

    public boolean isValidBST(TreeNode root) {
        inOrder(root);
        return result;
    }

    public void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        if (pre != null)
            result = pre < root.val;
        pre = root.val;
        inOrder(root.right);
    }

    public boolean isValidBST2(TreeNode root) {
        Integer pre = null;
        while (root != null) {
            if (root.left != null) {
                TreeNode node = getMostRight(root);
                if (node.right == null) {
                    node.right = root;
                    root = root.left;
                    continue;
                } else if (node.right == root) {
                    node.right = null;
                }
            }

            if (pre != null && pre > root.val)
                return false;
            pre = root.val;
            root = root.right;
        }
        return true;
    }

    private TreeNode getMostRight(TreeNode root) {
        if (root.left == null) return root;
        TreeNode node = root.left;
        while (node.right != null && node.right != node) {
            node = node.right;
        }
        return node;
    }

}
